package main

import (
	"fmt"
	"sort"
)

//官方排序取前k位:28ms 52%, 6.4MB 87%
func getLeastNumbers(arr []int, k int) []int {
	res := sort.IntSlice(arr)
	res.Sort()
	return res[:k]
}

//快速排序:20ms 93%,6.4MB 69%
func getLeastNumbers1(arr []int, k int) []int {
	if k >= len(arr) {
		return arr
	}
	quickSort(arr, k, 0, len(arr)-1)
	return arr[:k]
}

func quickSort(arr []int, k, left, right int) {
	if left >= right {
		return
	}
	i, j := left, right
	for i < j {
		for i < j && arr[j] >= arr[left] {
			j--
		}
		for i < j && arr[i] <= arr[left] {
			i++
		}
		arr[i], arr[j] = arr[j], arr[i]
	}
	arr[left], arr[i] = arr[i], arr[left]
	if i > k {
		quickSort(arr, k, left, i-1)
	}
	if i < k {
		quickSort(arr, k, i+1, right)
	}
}

func main() {
	fmt.Println(getLeastNumbers([]int{1, 2, 4, 6566, 421, 3, 5, 463, 435, 232}, 6))
	fmt.Println(getLeastNumbers1([]int{0, 0, 2, 3, 2, 1, 1, 2, 0, 4}, 10))
}
